package study.lanqiao.com;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * 蓝桥杯十道题，除了“最优清零个数”题目代码还在调试中，其他题目已经AC，
 * 其中t3_3()，t5_2()是AC的代码，t3(),t3()_1,t3_2(),t5也是题解（非最优方法），AC题解看t3_3()，t5_2()
 */

public class t2022 {
    public static void main(String[] args) {
        //t1();
        //t2();
        //t3();
        //t3_2();
        //t3_3();
        //t4();
        //t5();
        //t5_2();
        //t6();
        //t7();
        //t8();
        //t9();
        t10();
    }

    /**
     * 灭鼠先锋
     */
    public static void t1(){
        //case 1:
        int[][] arr1 = new int[2][4];
        arr1[0][0] = 1;
        if (next(arr1)){
            System.out.print("V");
        }else{
            System.out.print("L");
        }
        //case 2:
        int[][] arr2 = new int[2][4];
        arr2[0][0] = 1;arr2[0][1] = 1;
        if (next(arr2)){
            System.out.print("V");
        }else{
            System.out.print("L");
        }
        //case 3:
        int[][] arr3 = new int[2][4];
        arr3[0][1] = 1;
        if (next(arr3)){
            System.out.print("V");
        }else{
            System.out.print("L");
        }
        //case 4:
        int[][] arr4 = new int[2][4];
        arr4[0][1] = 1;arr4[0][2] = 1;
        if (next(arr4)){
            System.out.print("V");
        }else{
            System.out.print("L");
        }
    }
    public static boolean pre(int[][] arr){
        int cnt = 0;
        for(int i = 0 ; i < 2 ; i++){
            for(int j = 0 ; j < 4 ; j++)
                cnt += arr[i][j] == 0 ? 1 : 0;
        }
        if (cnt == 1) return false;
        if (cnt == 2) return true;
        //只放一个
        for(int i = 0 ; i < 2 ; i++){
            for(int j = 0 ; j < 4 ; j++){
                if (arr[i][j] == 0){
                    arr[i][j] = 1;
                    boolean win = next(arr);
                    arr[i][j] = 0;
                    if (win) return true;
                }
            }
        }
        //同一行连续两个
        for (int j = 0 ; j < 3 ; j++){
            if (arr[0][j] == 0 && arr[0][j + 1] == 0){
                arr[0][j] = 1;arr[0][j + 1] = 1;
                boolean win = next(arr);
                arr[0][j] = 0;arr[0][j + 1] = 0;
                if (win) return true;
            }
        }
        for (int j = 0 ; j < 3 ; j++){
            if (arr[1][j] == 0 && arr[1][j + 1] == 0){
                arr[1][j] = 1;arr[1][j + 1] = 1;
                boolean win = next(arr);
                arr[1][j] = 0;arr[1][j + 1] = 0;
                if (win) return true;
            }
        }
        return false;
    }
    public static boolean next(int[][] arr){
        int cnt = 0;
        for(int i = 0 ; i < 2 ; i++){
            for(int j = 0 ; j < 4 ; j++)
                cnt += arr[i][j] == 0 ? 1 : 0;
        }
        if (cnt == 1) return true;
        if (cnt == 2) return false;
        //只放一个
        for(int i = 0 ; i < 2 ; i++){
            for(int j = 0 ; j < 4 ; j++){
                if (arr[i][j] == 0){
                    arr[i][j] = 1;
                    boolean win = pre(arr);
                    arr[i][j] = 0;
                    if (!win) return false;
                }
            }
        }
        //同一行连续两个
        for (int j = 0 ; j < 3 ; j++){
            if (arr[0][j] == 0 && arr[0][j + 1] == 0){
                arr[0][j] = 1;arr[0][j + 1] = 1;
                boolean win = pre(arr);
                arr[0][j] = 0;arr[0][j + 1] = 0;
                if (!win) return false;
            }
        }
        for (int j = 0 ; j < 3 ; j++){
            if (arr[1][j] == 0 && arr[1][j + 1] == 0){
                arr[1][j] = 1;arr[1][j + 1] = 1;
                boolean win = pre(arr);
                arr[1][j] = 0;arr[1][j + 1] = 0;
                if (!win) return false;
            }
        }
        return true;
    }

    /**
     * 字母排列
     */
    public static void t2(){
        char[] chs = "WHERETHEREISAWILLTHEREISAWAY".toCharArray();
        Arrays.sort(chs);
        System.out.println(String.valueOf(chs));
    }

    /**
     * 质因数个数 - 通过用例20% - 内存不足
     */
    public static void t3(){
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        int len = (int)Math.sqrt(n);
        boolean[] zhishu = new boolean[len + 1];
        for (int i = 2; i <= len; i++) {
            if (zhishu[i]) continue;
            for (int j = i + i ; j <= len ; j += i){
                zhishu[j] = true;
            }
        }
        int cnt = 0;
        if (n % 2 == 0) cnt++;
        for (int i = 3 ; i <= Math.sqrt(n) ; i += 2){
            if (n % i == 0 && !zhishu[i]) cnt++;
        }
        System.out.println(cnt);
    }
    /**
     * 质因数个数 - 30%
     * 首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；
     *
     * 证明：令x≥1，将大于等于5的自然数表示如下：
     * ······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
     * 可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里有个题外话，关于孪生素数，有兴趣的道友可以再另行了解一下，由于与我们主题无关，暂且跳过。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。
     * 此时判断质数可以6个为单元快进，即将方法（2）循环中i++步长加大为6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被 6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可，理论上讲整体速度应该会是方法（2）的3倍。
     *
     */
    public static void t3_2(){
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long cnt = 0;
        if (n % 2 == 0) cnt++;
        if (n % 3 == 0) cnt++;
        for (int i = 5; i < Math.sqrt(n); i++) {
            if (n % i == 0 && (i % 6 == 1 || i % 6 == 5)){
                boolean isZhi = true;
                int cur = (int)Math.sqrt(i);
                for(int j = 5 ; j <= cur ; j++){
                    if (i % j == 0 || i % (j + 2) == 0){
                        isZhi = false;
                        break;
                    }
                }
                if (isZhi) cnt++;
            }
        }
        System.out.println(cnt);
    }
    /**
     * 质因数个数 - 时间复杂度0(sqrt(n)) - AC
     * 思路
     * 从2开始进行质因数分解，当n % i == 0的时候，说明我们遇见了一个质因数，cnt++。然后进入循环，以当前的约数为除数
     * 让n不断的除以当前的约数，直到不能整除。这一步的作用是为了保障之后n % i等于0的时候，i是质数
     * 由于n可能很大，且本身是一个质数，那么，我们设置i的时候，应该把i也设置为较大的数据类型，避免报错
     * 最后退出整个循环的时候，我们需要检查当前的n。
     * 由于我们不可能使用完全的暴力进行判断，这样肯定会超时，所以，我们的判断范围是化简过的。
     * 其次，由于我们进行了化简，那么数n的约数判断范围会缩小，众所周知，约数都是成对出现的，如果在小约数的时候结束了循环，那么，n的大约数我们就肯可能会遗漏。所以，当结束所有循环的时候，我们需要判断当前的n是否是质因数
     */
    public static void t3_3(){
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long cnt = 0;
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0){
                cnt++;
                while (n % i == 0){
                    n /= i;
                }
            }
        }
        if (n > 1) cnt++;
        System.out.println(cnt);
    }

    /**
     * 数位排序
     */
    public static void t4(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        Arrays.sort(arr,new Comparator<Integer>(){
            public int compare(Integer o1 , Integer o2){
                int sum1 = 0;
                int n1 = o1;
                while(n1 != 0){
                    sum1 += n1 % 10;
                    n1 /= 10;
                }
                int sum2 = 0;
                int n2 = o2;
                while(n2 != 0){
                    sum2 += n2 % 10;
                    n2 /= 10;
                }
                if (sum1 != sum2){
                    return sum1 - sum2;
                }else{
                    return o1 - o2;
                }
            }
        });
        System.out.println(arr[m - 1]);
    }

    /**
     * 技能升级
     */
    static class Node{
        public int index;
        public int val;
        public Node(int index,int val){
            this.index = index;
            this.val = val;
        }
    }
    static class MaxHeap{
        public Node[] arr;
        public int size;
        public MaxHeap(int n,int[] numArr){
            arr = new Node[n + 1];
            size = n;
            for (int i = 0 ; i < n ; i++){
                arr[i] = new Node(i,numArr[i]);
            }
            for (int i = n - 1 ; i >= 0 ; i--){
                heapify(i);
            }
        }
        public Node peek(){
            return size == 0 ? null : arr[0];
        }
        public void pop(){
            if (size == 0) return;
            arr[0] = arr[size - 1];
            size = size - 1;
            heapify(0);
        }
        public boolean isEmpty(){
            return size == 0;
        }
        public void heapify(int index){
            int parent = index;
            int left = 2 * parent + 1;
            int right = 2 * parent + 2;
            while(true){
                int maxIndex = left < size && arr[left].val > arr[parent].val ? left : parent;
                maxIndex = right < size && arr[right].val > arr[maxIndex].val ? right : maxIndex;
                if (maxIndex == parent){
                    break;
                }
                Node tmp = arr[parent];
                arr[parent] = arr[maxIndex];
                arr[maxIndex] = tmp;
                parent = maxIndex;
                left = 2 * parent + 1;
                right = 2 * parent + 2;
            }
        }
    }
    public static void t5(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        int[] sub = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            sub[i] = in.nextInt();
        }
        MaxHeap heap = new MaxHeap(n,arr);
        long res = 0;
        for (int i = 0; i < m && !heap.isEmpty(); i++) {
            Node cur = heap.peek();
            res += cur.val;
            cur.val = cur.val - sub[cur.index];
            if (cur.val <= 0){
                heap.pop();
            }else{
                heap.heapify(0);
            }
        }
        System.out.println(res);
    }

    /**
     * AC
     */
    public static void t5_2(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        int[] sub = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            sub[i] = in.nextInt();
        }
        int l = 0;
        int r = 1000000;
        while (l < r){
            int mid = (r + l + 1) / 2;
            if (check(mid,arr,sub,n,m)){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        int x = l;
        long res = 0;
        int cc = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] < x) continue;
            int cnt = 1 + (arr[i] - x) / sub[i];
            if (arr[i] - (cnt - 1) * sub[i] == x){
                cc++;
                cnt--;
            }
            if (m > cnt){
                m -= cnt;
                res += (long)cnt * (arr[i] + arr[i] - (cnt - 1) * sub[i]) / 2;
            }else{
                cnt = m;
                m = 0;
                res += (long)cnt * (arr[i] + arr[i] - (cnt - 1) * sub[i]) / 2;
                break;
            }
        }
        res += Math.min(m,cc) * x;
        System.out.println(res);
    }
    public static boolean check(int x,int[] arr,int[] sub,int n,int m){
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] < x) continue;
            cnt += 1 + (arr[i] - x) / sub[i];
            if (cnt >= m) return true;
        }
        return false;
    }

    /**
     * 重新排序
     */
    public static void t6(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int[] cntArr = new int[n + 1];
        int m = in.nextInt();
        int left = 0,right = 0;
        for (int i = 0; i < m; i++) {
            left = in.nextInt() - 1;
            right = in.nextInt() - 1;
            cntArr[left]++;
            cntArr[right + 1]--;
        }
        for (int i = 1; i < n; i++) {
            cntArr[i] += cntArr[i - 1];
        }
        long sum1 = 0;
        long sum2 = 0;
        for (int i = 0; i < n; i++) {
            //System.out.print(cntArr[i] + " ");
            sum1 += ((long)arr[i]) * cntArr[i];//arr[i] * cntArr[i];注意此处要先强转成long，否则相乘后超出int范围会发生字段被截取，导致结果不正确
        }
        Arrays.sort(arr);
        //此处要将cntArr最后一个元素设为无穷大，因为cntArr长度是n+1，升序排列时cntArr[n]为0或负数，会影响结果
        cntArr[n] = Integer.MAX_VALUE;
        Arrays.sort(cntArr);

        for (int i = 0; i < n; i++) {
            //System.out.print(cntArr[i] + " ");
            sum2 += ((long)arr[i]) * cntArr[i];//arr[i] * cntArr[i];
        }
        System.out.println(sum2 - sum1);
    }

    /**
     * 最优清零方案 - 采用线段树，通过10%，还在调试中
     */
    /**
     * 构建线段树，线段树知识可参考网址：https://www.cnblogs.com/xenny/p/9801703.html
     */
    static class TNode{
        public long l;//左区间
        public long r;//右区间
        public long minVal;//区间最小值
        public long minPos;//最小值所在数组下标
        public long sum;//区间和
        public long lazz;//懒标签
        public TNode(long l,long r,long minVal,long minPos,long sum,long lazz){
            this.l = l;
            this.r = r;
            this.minVal = minVal;
            this.minPos = minPos;
            this.sum = sum;
            this.lazz = lazz;
        }
        public TNode(){}
    }
    static class Tree{
        TNode[] tree;
        public Tree(int size){
            tree = new TNode[size<<2];
        }
        public void push_up(int i,long l,long r){
            long minVal = tree[i<<1].minVal < tree[i<<1|1].minVal ? tree[i<<1].minVal : tree[i<<1|1].minVal;
            long minPos = tree[i<<1].minVal < tree[i<<1|1].minVal ? tree[i<<1].minPos : tree[i<<1|1].minPos;
            long sum = tree[i<<1].sum + tree[i<<1|1].sum;
            tree[i].l = l;
            tree[i].r = r;
            tree[i].minVal = minVal;
            tree[i].minPos = minPos;
            tree[i].sum = sum;
            //= new TNode(l,r,minVal,minPos,sum,0);
        }

        /**
         *
         * @param i：区间下标
         * @param l：左边界
         * @param r：右边界
         * @param arr：数组
         */
        public void build(int i,int l,int r,int[] arr){
            if (l == r){
                tree[i] = new TNode(l,r,arr[l],l,arr[l],0);
                return;
            }
            tree[i] = new TNode();
            tree[i].lazz = 0;
            int mid = (l + r) >> 1;
            build(i<<1,l,mid,arr);
            build(i<<1|1,mid+1,r,arr);
            push_up(i,l,r);
        }
        public void build_down(int i){
            if (tree[i].lazz == 0) return;
            if (tree[i<<1] != null){
                tree[i<<1].lazz += tree[i].lazz;
                tree[i<<1].minVal -= tree[i].lazz;
                tree[i<<1].sum -= tree[i].lazz * (tree[i<<1].r - tree[i<<1].l + 1);
            }
            if (tree[i<<1|1] != null){
                tree[i<<1|1].lazz += tree[i].lazz;
                tree[i<<1|1].minVal -= tree[i].lazz;
                tree[i<<1|1].sum -= tree[i].lazz * (tree[i<<1|1].r - tree[i<<1|1].l + 1);

            }
            tree[i].lazz = 0;
        }

        /**
         *
         * @param i：区间下标
         * @param l：左边界
         * @param r：右边界
         * @return [l,r]区间的和
         */
        public long sum(int i,long l,long r){
            if (tree[i].l >= l && tree[i].r <= r){
                return tree[i].sum;
            }
            build_down(i);
            long sum1 = 0;
            if (tree[i<<1] != null && l <= tree[i<<1].r){
                sum1 += sum(i<<1,l,r);
            }
            if (tree[i<<1|1] != null && r >= tree[i<<1|1].l){
                sum1 += sum(i<<1|1,l,r);
            }
            //push_up(i,l,r);
            return sum1;
        }

        /**
         *
         * @param i：区间下标
         * @param l：左边界
         * @param r：右边界
         * @return 0：最小值 1：最小值下标
         */
        public long[] getMin(int i,long l,long r){
            if (tree[i].l >= l && tree[i].r <= r){
                return new long[]{tree[i].minVal,tree[i].minPos};
            }
            build_down(i);
            long[] min1 = null;
            long[] min2 = null;
            if (tree[i<<1] != null && l <= tree[i<<1].r){
                min1 = getMin(i<<1,l,r);
            }
            if (tree[i<<1|1] != null && r >= tree[i<<1|1].l){
                min2 = getMin(i<<1|1,l,r);
            }
            if (min1 == null) return min2;
            if (min2 == null) return min1;
            return min1[0] < min2[0] ? min1 : min2;
            //return //min1 != null && min1[0] < min2[0] ? min1 : min2;
        }
        public void modify(int i,long l,long r,long v){
            if (tree[i].l >= l && tree[i].r <= r){
                tree[i].minVal -= v;
                tree[i].lazz += v;
                tree[i].sum -= v * (tree[i].r - tree[i].l + 1);
                return;
            }
            build_down(i);
            if (tree[i<<1] != null && l <= tree[i<<1].r){
                modify(i<<1,l,r,v);
            }
            if (tree[i<<1|1] != null && r >= tree[i<<1|1].l){
                modify(i<<1|1,l,r,v);
            }
            if (tree[i<<1] != null && tree[i<<1|1] != null) push_up(i,l,r); //非叶子区间
        }
    }
    public static void t7(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = in.nextInt();
        }
        int res = 0;
        Tree mytree = new Tree(n + 10);
        mytree.build(1,1,n,arr);
        long l = 1,r = Math.min(n,m);
        while (l <= n){
            if (mytree.sum(1,l,l) == 0){
                l++;
                r = Math.min(l + m - 1,n);
                continue;
            }
            if (r == l + m - 1){
                long[] minArr = mytree.getMin(1,l,r);
                long minVal = minArr[0];
                long minPos = minArr[1];
                res += minVal;
                mytree.modify(1,l,r,minVal);
                if (l < minPos){
                    res += mytree.sum(1,l,minPos - 1);
                }
                l = minPos + 1;
                r = Math.min(l + m - 1,n);
            }else{
                res += mytree.sum(1,l,r);
                break;
            }
        }
        System.out.println(res);
    }

    /**
     * 爬树的甲壳虫
     * 逆元知识 - 模为质数 - 费马小定理 https://www.cnblogs.com/BLeaves/p/8651163.html
     * 快速幂
     * 期望dp https://blog.csdn.net/qq_36408082/article/details/124089032
     * https://blog.csdn.net/weixin_45697774/article/details/104274160
     */
    //x^y % mod
    public static long pow(long x,long y,long mod){
        long res = 1;
        long base = x;
        while (y > 0){
            if ((y & 1) != 0){
                res *= base;
            }
            base *= base;
            res %= mod;
            base %= mod;
            y >>= 1;
        }
        return res;
    }
    public static void t8(){
        Scanner in = new Scanner(System.in);
        long mod = 998244353;
        int n = in.nextInt();
        int[] xArr = new int[n + 1];
        int[] yArr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            xArr[i] = in.nextInt();
            yArr[i] = in.nextInt();
        }
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = (dp[i - 1] + 1) * (yArr[i] % mod);
            dp[i] %= mod;
            dp[i] *= pow(yArr[i] - xArr[i],mod - 2,mod);
            dp[i] %= mod;
        }
        System.out.print(dp[n]);
    }

    /**
     * 推导部分和
     */
    static class UF{
        private int[] fa;
        private long[] d;
        public UF(int n){
            fa = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
            }
            d = new long[n + 1];
        }
        public int find(int x){
            if (x == fa[x]) return x;
            int root = find(fa[x]);
            d[x] += d[fa[x]];
            fa[x] = root;
            return root;
        }
        public boolean merge(int u,int v,long sum){
            int x = find(u);
            int y = find(v);
            if (x == y) return false;
            fa[x] = y;
            d[x] = sum + d[v] - d[u];
            return true;
        }
        public void getSum(int l,int r,StringBuilder sb){
            if (find(l) != find(r)){
                sb.append("UNKNOWN");
                //System.out.println("UNKNOWN");
            }else{
                sb.append((d[l] - d[r]));
            }
            //System.out.println(d[l] - d[r]);
        }
    }
    public static void t9(){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        UF uf = new UF(n);
        int m = in.nextInt();
        int q = in.nextInt();
        int l = 0,r = 0;
        long s = 0;
        for (int i = 0; i < m; i++) {
            l = in.nextInt();
            r = in.nextInt();
            s = in.nextLong();
            uf.merge(l - 1,r,s);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            l = in.nextInt();
            r = in.nextInt();
            uf.getSum(l - 1,r,sb);
            if (i < q - 1) sb.append("\n");
        }
        System.out.print(sb.toString());
    }

    /**
     * 蜂巢
     * 1.以水平轴作为x轴，西偏北60°作为y轴求出蜂巢对应的坐标(x,y)
     * 2.计算两个点(x1,y1)与(x2,y2)之间的距离时，令点(x1,y1)在点(x2,y2)的左部
     * 3.若点(x1,y1)在点(x2,y2)的上方，则 minVal = Math.abs(left[0] - right[0]) + Math.abs(left[1] - right[1])
     * 4.若点(x1,y1)在点(x2,y2)的下方，则 minVal = Math.max(Math.abs(left[0] - right[0]) , Math.abs(left[1] - right[1]));
     */
    /**
     *
     * @param d
     * @param p
     * @param q
     * @return 0：蜂巢横坐标 1：蜂巢纵坐标
     */
    public static int[] getPos(int d,int p,int q){
        int[] pos = new int[2];
        switch (d){
            case 0:
                pos[0] = q-p; //横坐标：水平线，
                pos[1] = q; //纵坐标：西偏北60°
                break;
            case 1:
                pos[0] = q;
                pos[1] = p;
                break;
            case 2:
                pos[0] = p;
                pos[1] = p - q;
                break;
            case 3:
                pos[0] = p - q;
                pos[1] = - q;
                break;
            case 4:
                pos[0] = - q;
                pos[1] = - p;
                break;
            case 5:
                pos[0] = - p;
                pos[1] = q - p;
                break;
            default:
                break;
        }
        return pos;
    }

    public static void t10(){
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        int d1,p1,q1,d2,p2,q2;
        StringBuilder sb =  new StringBuilder();
        while (t-- > 0){
            d1 = in.nextInt();
            p1 = in.nextInt();
            q1 = in.nextInt();
            d2 = in.nextInt();
            p2 = in.nextInt();
            q2 = in.nextInt();
            int[] a1 = getPos(d1,p1,q1);
            int[] a2 = getPos(d2,p2,q2);
            int[] left = null,right = null;
            if (a1[0] <= a2[0]){
                left = a1;
                right = a2;
            }else{
                left = a2;
                right = a1;
            }
            int minVal = 0;
            if (left[1] > right[1]){
                minVal = Math.abs(left[0] - right[0]) + Math.abs(left[1] - right[1]);
            }else{
                minVal = Math.max(Math.abs(left[0] - right[0]) , Math.abs(left[1] - right[1]));
            }
            sb.append(minVal + "\n");
        }
        System.out.println(sb.toString());
    }
}
